package LinkedListPackage2;

import LinkedListPackage.ListNode;

/**
 * @author Lzm
 * @version 1.0
 */
public class detectCycle_ {

  public ListNode detectCycle(ListNode head) {
   if (head == null){
     return null;
   }

   if (head.next == null){
     return null;
   }
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    ListNode fast = dummyHead;
    ListNode slow = dummyHead;
    while(fast.next.next != null){
      fast = fast.next.next;
      slow = slow.next;
      if (slow == fast){
        ListNode temp1 = dummyHead;
        ListNode temp2 = fast;
        while(temp1 != temp2){
          temp1 = temp1.next;
          temp2 = temp2.next;
        }
        return temp1;
      }
    }
    // x + y / 1 = x + n(z + y) + y / 2
    // 2x + 2y = x + nz + ny + y
    // x + y = n(z + y)
    // 若n = 1;
    // x=z
    return null;
  }
}
